import sun.plugin.javascript.navig.Link;

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class project {
    List<List<Integer>> list=new ArrayList<>();
    Deque<Integer> deque=new ArrayDeque<>();
    public void dfs(TreeNode root,int target){
        if(root==null){
            return;
        }
        deque.offerLast(root.val);
        target-=root.val;
        if(root.left==null&&root.right==null&&target==0){
            list.add(new LinkedList<>(deque));
        }
        dfs(root.left,target);
        dfs(root.right,target);
        deque.pollLast();
    }
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        dfs(root,target);
        return list;
    }












    public int[] singleNumbers(int[] nums) {
        int count=0;
        for(int i : nums){
            count^=i;
        }
        int div=1;
        while((div&count)==0){
            div<<=1;
        }
        int a=0;
        int b=0;
        for(int i : nums){
            if((div&i)!=0){
                a^=i;
            }else{
                b^=i;
            }
        }
        return new int[]{a,b};
    }








    public int[] levelOrder(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        if(root!=null){
            queue.add(root);
            while(!queue.isEmpty()){
                int size=queue.size();
                for(int i=0;i<queue.size();i++){
                    TreeNode tmp=queue.poll();
                    list.add(tmp.val);
                    if(tmp.left!=null){
                        queue.add(tmp.left);
                    }
                    if(tmp.right!=null){
                        queue.add(tmp.right);
                    }
                }
            }
        }
        int[] arr=new int[list.size()];
        int i=0;
        for(int n : list){
            arr[i++]=n;
        }
        return arr;
    }











    public List<List<Integer>> levelOrder1(TreeNode root) {
        Queue<TreeNode> stack=new LinkedList<>();
        List<List<Integer>> list=new ArrayList<>();
        if(root!=null){
            stack.offer(root);
            while(!stack.isEmpty()){
                int size=stack.size();
                LinkedList<Integer> arr=new LinkedList<>();
                for(int i=0;i<size;i++){
                    TreeNode tmp=stack.poll();
                    if(list.size()%2==0){
                        arr.addLast(tmp.val);
                    }else{
                        arr.addFirst(tmp.val);
                    }
                    if(tmp.left!=null){
                        stack.add(tmp.left);
                    }
                    if(tmp.right!=null){
                        stack.add(tmp.right);
                    }
                }
                list.add(arr);
            }
        }
        return list;
    }











    public List<List<Integer>> levelOrder2(TreeNode root) {
        Stack<TreeNode> stack=new Stack<>();
        List<List<Integer>> list=new ArrayList<>();
        if(root!=null){
            stack.push(root);
            while(!stack.isEmpty()){
                int size=stack.size();
                List<Integer> arr=new ArrayList<>();
                if(list.size()%2==0){
                    for(int i=0;i<size;i++){
                        TreeNode tmp=stack.pop();
                        arr.add(tmp.val);
                        if(tmp.left!=null){
                            stack.push(tmp.left);
                        }
                        if(tmp.right!=null){
                            stack.push(tmp.right);
                        }
                    }
                }else{
                    for(int i=0;i<size;i++){
                        TreeNode tmp=stack.pop();
                        arr.add(tmp.val);
                        if(tmp.right!=null){
                            stack.push(tmp.right);
                        }
                        if(tmp.left!=null){
                            stack.push(tmp.left);
                        }
                    }
                }
                list.add(arr);
            }
        }
        return list;
    }











    public boolean dfs2(TreeNode A,TreeNode B){
        if(B==null){
            return true;
        }
        if(A==null||B.val!=A.val){
            return false;
        }
        return dfs2(A.left,B.left)&&dfs2(A.right,B.right);
    }
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A==null&&B==null){
            return true;
        }
        if(A==null||B==null){
            return false;
        }
        return dfs2(A,B)||isSubStructure(A.left,B)||isSubStructure(A.right,B);
    }









    public int maxArea(int[] height) {
        int max=0;
        int left=0;
        int right=height.length-1;
        while(left<right){
            int Max=Math.min(height[left],height[right])*(right-left);
            max=Math.max(max,Max);
            if(height[left]<=height[right]){
                left++;
            }else{
                right--;
            }
        }
        return max;
    }










    public int removeDuplicates(int[] nums) {
        if(nums.length<=2){
            return 2;
        }
        int left=2;
        int right=2;
        while(right<nums.length){
            if(nums[left-2]!=nums[right]){
                nums[left]=nums[right];
                left++;
            }
            right++;
        }
        return left;
    }























    public boolean search(int[] nums, int target) {
        int len=nums.length;
        if(len==0){
            return false;
        }else if(len==1){
            return nums[0]==target;
        }
        int left=0;
        int right=len-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(nums[mid]==target){
                return true;
            }
            if(nums[left]==nums[mid]&&nums[right]==nums[mid]){
                left++;
                right--;
            }else if(nums[left]<=nums[mid]){
                if(nums[left]<=target&&nums[mid]>target){
                    right=mid-1;
                }else{
                    left=mid+1;
                }
            }else{
                if(nums[mid]<target&&nums[right]>=target){
                    left=mid+1;
                }else{
                    right=mid-1;
                }
            }
        }
        return false;
    }








    public int numTrees(int n) {
          int[] dp=new int[n+1];
          dp[0]=1;
          dp[1]=1;
          for(int i=2;i<=n;i++){
              for(int j=1;j<=i;j++){
                  dp[i]+=dp[j-1]*dp[i-j];
              }
          }
          return dp[n];
    }







    public boolean dfs1(TreeNode root,long left,long right){
        if(root==null){
            return true;
        }
        if(root.val<=left||root.val>=right){
            return false;
        }
        return dfs1(root.left,left,root.val)&&dfs1(root.right,root.val,right);
    }
    public boolean isValidBST(TreeNode root) {
        return dfs1(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }
}
